#include <iostream>
#include <fstream>
#include <vector>
#include <cassert>
using namespace std;

typedef int keytype;

int partition(vector<keytype> &keys, int low, int high)
{
  keytype k;

  k = keys[low];
  while (low < high){
    while (high > low && keys[high] >= k)
      high--;
    keys[low] = keys[high];
    while (low < high && keys[low] <= k)
      low++;
    keys[high] = keys[low];
  }
  keys[low] = k;
  return low;
}

void rquick(vector<keytype> &keys, int low, int high)
{
  int loc;

  if (low < high){
    loc = partition(keys, low, high);
    rquick(keys, low, loc-1);
    rquick(keys, loc+1, high);
  }
  
}

void quick(vector<keytype> &keys)
{
  rquick(keys, 0, keys.size()-1);
}

void print(vector<keytype> &keys)
{
  for (auto it = keys.begin(); it != keys.end(); it++)
    cout << *it << "\t";
  cout << endl;
}

int main()
{
  ifstream in("sort.txt");
  vector<keytype> keys;
  keytype k;

  assert(in);
  while (in >> k)
    keys.push_back(k);

  quick(keys);
  print(keys);
  in.close();

  return 0;
}
